Graphs & Topological Sort

Topological sort dominates Snowflake's graph reports more than any other single pattern, so if you budget your graph prep unevenly, spend it here. A topological sort answers one question. Given a pile of steps where some must finish before others can start, what order lets you run them? And is that even possible, or did somebody wire a cycle into the dependencies? The prerequisite-ordering problems and their weighted, level-counting variants are the recurring shapes, and they sit at the top of what candidates report from these rounds.

The reason it recurs is not subtle for a company that schedules dependent work for a living. A data platform is full of steps that wait on other steps. A task fires only after the task it depends on lands. A join cannot run until both its inputs are materialized, a refresh of a derived table waits on the tables it reads. Every one of those is a directed acyclic graph, and ordering a DAG so each node comes after everything it depends on is exactly topological sort. The interviewer reaches for the course-prerequisite phrasing because it is the cleanest way to ask the question the team answers all day.

The Snowflake angle

Pin down whether the graph can even have a cycle before you pick an algorithm. Snowflake interviewers reward the candidate who gathers constraints first, and on a dependency problem the load-bearing constraint is acyclicity. Ask it out loud: "Are these guaranteed to form a DAG, or do I need to detect a cycle and report it?" If a cycle is possible, your topological sort has to double as cycle detection, and Kahn's algorithm gives you that for free, because a graph with a cycle never drains its queue. State that you will return an empty ordering (or flag the cycle) when the count of processed nodes falls short of the total. That one sentence shows you know the failure mode, which on a scheduling graph is the whole reason the question is interesting.

SnowflakePremium lesson · Coding round

The 2 Snowflake problems are below.

1. 1A Premium questionCoding · Hard · Signature problem
2. 2A Premium questionCoding · Medium · Signature problem

Each with hints, the follow-up and a tested solution.

Get the Snowflake questions

$49 a year · all 100 companies · cancel anytime

From 111 Snowflake reports, forum threads behind logins and write-ups in Chinese.

Read a free Snowflake lesson firstAlready a member? Sign in